518. 零钱兑换 II

Similar Question

Solution Tips

方案一: 完全背包求组合方案数量

var change = function(amount, coins) {
    // 完全背包问题 + 组合方式
    const n = coins.length;
    // 1. 在 总值为 j 时, 使用 [0-i] 面额的硬币, 有多少种组合方式
    const dp = Array.from({ length: amount + 1 }, () => 0);
    // 3. 在总值为 0 时, 不能选择任何硬币, 只有 1 种方法
    dp[0] = 1;

    for (let i = 0; i < n; i++) {
        for (let j = coins[i]; j <= amount; j++) {
            // 2. 使用当前硬币后, 剩余的空间直接参考已有的方案总数为 dp[j - coins[i]]
            // 不使用当前硬币, 则方案数和之前的一样, 即: dp[j]
            dp[j] += dp[j - coins[i]];
        }
        // console.log(dp.concat());
    }

    return dp[amount];
};
let amount = 5, coins = [1, 2, 5]
console.log(change(amount, coins));

完全背包求组合方案数量, 先遍历物品, 再遍历容量

如果是调换了 for 循环的顺序, 先遍历容量, 再遍历物品, 就是变成求排列数量了, 因为同一个容量, 会经过优先放 物品 1 和物品 2 的情况, 然后在优先放物品 2 的时候, 也是放了物品 1 的, 就变成了 {2, 1} 和 {1, 2} 是两种方案了